import java.util.Arrays;

/**
 * @author:gao
 * @date:2020/6/24
 * @time:13:24
 * @version:0.0.1
 * @description:none
 */

//16. 最接近的三数之和 15的进阶版

/*
* 双指针问题是把 n方的问题优化成n
* 这个三指针的问题本质上就是双指针再套一层循环
* */


//five解法，二重循环+折半查找 n放logn
//class Solution {
//    public int threeSumClosest(int[] nums, int target) {
//        Arrays.sort(nums);
//        int min_diff = Integer.MAX_VALUE;
//        int ans = Integer.MAX_VALUE;
//        for(int i=0;i<nums.length-2;i++){
//            for(int j=i+1;j<nums.length-1;j++){
//                int sum = nums[i]+nums[j];
//                int index = Arrays.binarySearch(nums,j+1,nums.length,target-sum);
//                if(index<0){
//                    index = -index-1; //应该插入的位置
//                    if(index==nums.length){
//                        if(Math.abs(target-sum-nums[index-1])<min_diff){
//                            ans = sum+nums[index-1];
//                            min_diff = Math.abs(target-sum-nums[index-1]);
//                        }
//                    }
//                    else if(index==j+1){
//                        if(Math.abs(target-sum-nums[index])<min_diff){
//                            ans = sum+nums[index];
//                            min_diff = Math.abs(target-sum-nums[index]);
//                        }
//                    }else{
//                        if(Math.abs(target-sum-nums[index-1])<min_diff){
//                            ans = sum+nums[index-1];
//                            min_diff = Math.abs(target-sum-nums[index-1]);
//                        }
//                        if(Math.abs(target-sum-nums[index])<min_diff){
//                            ans = sum+nums[index];
//                            min_diff = Math.abs(target-sum-nums[index]);
//                        }
//                    }
//
//                }else{
//                   return target;
//                }
//            }
//        }
//        return ans;
//    }
//}
//
//    //循环low 然后 mid 和 high向中间靠
//    public static int threeSumClosest(int[] nums, int target) {
//        Arrays.sort(nums);//先排序
//        int minGap = Integer.MAX_VALUE;//间隔值，保存的是最小间隔值
//        int res = Integer.MAX_VALUE;//返回的数据
//        for (int i = 0; i < nums.length - 2; i++) {
//            int lo = i + 1, hi = nums.length - 1;
//            while (lo < hi) {
//                int sum = nums[i] + nums[lo] + nums[hi];
//                int tempMinGap = target - sum;
//                if (Math.abs(tempMinGap) < Math.abs(minGap)) {
//                    minGap = tempMinGap;
//                    res = sum;
//                }
//                if (tempMinGap == 0)
//                    return target;
//                else if (tempMinGap > 0)
//                    lo++;
//                else
//                    hi--;
//            }
//        }
//        return res;
//    }